package club.banyuan;

public class MyLinkedList<E> {

  // 定义节点的数据结构
  protected static class Node<E> {
    private final E item; // 节点存放的数据
    private Node<E> next; // 下一个节点

    // 构造一个节点
    public Node(E item) {
      this.item = item;
      this.next = null;
    }

    public E getItem() {
      return item;
    }

    public Node<E> getNext() {
      return next;
    }

    public void setNext(Node<E> next) {
      this.next = next;
    }

    @Override
    public String toString() {
      return item.toString();
    }
  }

  protected Node<E> head; // 链表的头结点
  protected int length; // 链表里面有多少个元素

  public MyLinkedList() {
    head = null;
    length = 0;
  }

  public boolean add(E data, int pos) {
    // 判断非法位置
    if (pos < 0 || pos > length) {
      return false;
    }

    // 在pos位置插入一个节点
    // 1. 构造新的节点 newNode
    var newNode = new Node<E>(data);

    if (pos == 0) {
      // 在头部插入一个新的节点
      // 1)新节点指向现在的头结点
      newNode.next = head;
      // 2)头结点变更为新节点
      head = newNode;
    } else {
      // 非头部插入
      // 2. 先找到pos-1位置的节点（pre）
      var pre = head;
      for (int i = 0; i < pos - 1; i++) {
        pre = pre.next;
      }
      // 3. 新节点指向after节点：newNode->next = pre->next
      newNode.next = pre.next;
      // 4. pre节点指向新节点:
      pre.next = newNode;
    }
    length++;
    return true;
  }

  public E remove(int pos) {
    // 判断pos是否合法
    if (pos < 0 || pos >= length) {
      return null;
    }

    E r = null; // 返回被删除节点里面的数据

    if (pos == 0) {
      // 删除当前的head
      r = head.item;
      head = head.next;
    } else {
      // 1. 找到pos - 1: pre
      var pre = head;
      for (int i = 0; i < pos - 1; i++) {
        pre = pre.next;
      }
      r = pre.next.item;
      // 2. pre.next = pre.next.next;
      pre.next = pre.next.next;
    }
    length--;
    return r;
  }

  public int size() {
    return length;
  }

  public boolean addAtHead(E e) {
    return add(e, 0);
  }

  public boolean addAtTail(E e) {
    return add(e, length);
  }

  public E removeHead() {
    return remove(0);
  }

  public E removeTail() {
    return remove(length - 1);
  }

  public boolean isEmpty() {
    return length == 0;
  }

  @Override
  // TODO 作业：完善toString 方法
  public String toString() {
    StringBuilder builder = new StringBuilder();
    builder.append(this.getClass().getSimpleName());
    builder.append(": {");
    var len = length;
    if (len > 0) {
      var temp = head;
      while (len > 0) {
        builder.append(temp).append(" -> ");
        temp = temp.next;
        len--;
      }
      builder.delete(builder.length() - 4, builder.length());
    }
    builder.append("}");
    return builder.toString();
  }

  /**
   * 返回链表中e数据对应的位置
   *
   * @param e - Node里面的item
   * @return 对应的序号， 如果找不到这个元素， 则返回-1 {9 -> 8 -> 7 -> 6 -> 5 -> 4 -> 3 -> 2 -> 1 -> 0} search(6) ->
   *     3; search(10) -> -1
   */
  // TODO 作业：完成search方法
  public int find(E e) {
    return 0;
  }

  /**
   * 返回pos对应位置的节点
   *
   * @param pos 索引
   * @return 索引对应的节点
   */
  public Node<E> get(int pos) {
    if (pos < 0 || pos >= length) return null;
    var r = head;
    for (int i = 0; i < pos; i++) r = r.next;
    return r;
  }
}
